//自己
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        //1. 先排序
        sort(nums.begin(), nums.end());
        //2. 固定一个数+左右双指针+单调性 找三元组
        for (int i=0; i < n; i++)
        {
            //注意: i==0时跳过, 否则i-1越界
            if (i!=0 && nums[i] == nums[i-1])//跳过相同元素(因为遍历的结果会与前一个相同); 
                continue;
            
            int left = i+1, right = n-1;
            int contrary = -nums[i];//contrary相反的 
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                                                        //cout << contrary<< " " << sum << endl;
                if (sum > contrary)  --right;
                else if (sum < contrary) ++left;
                else //(sum = contrary) 
                {
                    ret.push_back({nums[left], nums[right], nums[i]});//initerlizer的隐式类型转换
                    //left, right同时移动, 如果下一个元素与前一个元素相同, 则继续跳过
                    ++left;
                    --right;
                    while (left < right)//防止越界
                    {
                        if (nums[left] == nums[left-1])  ++left;
                        else break;
                    }
                    while (left < right)
                    {
                        if (nums[right] == nums[right+1]) --right;
                        else break;
                    }
                }
            }
        } 
        return ret;
    }
};


//答案
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        //1. 先排序
        sort(nums.begin(), nums.end());
        //2. 固定一个数+左右双指针+单调性 找三元组
        for (int i=0; i < n; ) 
        {
            int left = i+1, right = n-1, target = -nums[i];//target 目标
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)  --right;
                else if (sum < target) ++left;
                else //(sum = target) 
                {
                    ret.push_back({nums[left], nums[right], nums[i]});//initerlizer的隐式类型转换
                    //不漏 + 去重   left, right同时移动, 如果下一个元素与前一个元素相同, 则继续跳过
                    ++left, --right;
                    while (left < right && nums[left]==nums[left-1]) ++left;
                    while (left < right && nums[right]==nums[right+1]) --right;
                }
            }
            //去重i, 不能越界
            ++i;
            while (i<n && nums[i] == nums[i-1]) ++i;//跳过相同元素(因为遍历的结果会与前一个相同); 
        } 
        return ret;
    }
};
//时间 O(n*logn + n^2)
//空间 O(logN);//主要是快排内递归栈帧的开销